운영체제에서 특정 메모리를 물리 메모리에 올리려 하는데, 물리 메모리가 다 차있는 경우

기존 페이지 중 하나를 물리 메모리에서 저장 매체로 내리고(저장)

새로운 페이지를 해당 물리 메모리 공간에 올려야 한다.(교체)

선입 선출

앞으로 가장 오랫동안 사용하지 않을 페이지를 내리자->일반 OS에서는 구현 불가능

가장 오래 전에 사용된 페이지를 교체

OPT 교체 알고리즘이 구현이 불간으하므로, 과거 기록을 기반으로 시도

가장 적게 사용된 페이지를 교체

LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체하는 기법

각 페이지마다 참조 비트(R), 수정 비트(M)을 둠(R, M)

    (0,0), (0,1), (1,0), (1,1) 순으로 페이지 교체

메모리 지역성: 코드가 실행되고난 후, 주변의 알고리즘이 사용될 가능성이 크다.

-> LRU 기법의 효율성의 근거가 된다.

반복적으로 데이터 폴트가 발생해서, 과도하게 페이지 교체 작업이 일어나, 실제로는 아무일도 하지 못하는 상황

일정 수준이상 degree of multiprogramming이 증가하면, CPU Utilization이 급격하게 감소됨.